package pers.vic.basics.leetcode;

import java.util.Arrays;

/**
 * @author Vic.xu
 * @description: 87. 扰乱字符串 {@literal https://leetcode-cn.com/problems/scramble-string/}
 * @date: 2021/3/3 0003 9:35
 */
public class J0087_H_IsScramble {

    /*
    给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。
     在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。将会产生扰乱字符串
     给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
     */

    /**
     * 先用递归的方式尝试一下啊
     */
    public static boolean isScramble(String s1, String s2) {
        //一些判断
        if (s1 == null || s2 == null) {
            return false;
        }
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        // 判断两个字符串中的字符是否一致
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        Arrays.sort(cs1);
        Arrays.sort(cs2);
        if (!new String(cs1).equals(new String(cs2))) {
            return false;
        }
        //开始切分
        for (int i = 1; i < s1.length(); i++) {
            // 如果前后半段 都是干扰字符串  比如这样切分 g reat   r geat
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {
                return true;
            }
            // 如果各交叉比对   如此分割  g reat     reat  g
            if (isScramble(s1.substring(0, i), s2.substring(s1.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s1.length() - i))) {
                return true;

            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isScramble("abc","bca"));
        System.out.println(isScramble("great","rgeat"));
        System.out.println(isScramble("abcde","caebd"));


        String str1 = "abc";
        String str2 = "cba";
        for (int i = 1; i < str1.length(); i++) {
           String a = str1.substring(0, i) + " : " + str2.substring(0, i);
           String b = str1.substring(i) + " : " + str2.substring(i);

            String c = str1.substring(0, i) + " : " + str2.substring(str1.length() - i);
            String d = str1.substring(i) + " : " + str2.substring(0, str1.length() - i);
            System.out.println("前后：" + a + "  "+b);
            System.out.println("交叉：" + c + "  "+d);


        }
    }

}
